package com.jack.leetcode.eachproblem_2020;

public class 排序链表 {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode fast = new ListNode(head.next.val);
        ListNode slow = new ListNode(head.val);
        ListNode first = fast, second = slow, left = head.next, right = head;
        while(left.next != null && left.next.next != null){
            first.next = new ListNode(left.next.next.val);
            left = left.next.next;
            first = first.next;
        }
        while(right.next != null && right.next.next != null){
            second.next = new ListNode(right.next.next.val);
            right = right.next.next;
            second = second.next;
        }
        return merge(sortList(fast), sortList(slow));
    }

    private static ListNode merge(ListNode left, ListNode right){
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        ListNode result = new ListNode(-1);
        ListNode tmp = result;
        while(left != null && right != null){
            if(left.val < right.val){
                tmp.next = new ListNode(left.val);
                left = left.next;
            }else{
                tmp.next = new ListNode(right.val);
                right = right.next;
            }
            tmp = tmp.next;
        }
        while(left != null){
            tmp.next = new ListNode(left.val);
            tmp = tmp.next;
            left = left.next;
        }
        while(right != null){
            tmp.next = new ListNode(right.val);
            tmp = tmp.next;
            right = right.next;
        }
        return result.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(6);
        head.next.next.next.next.next = new ListNode(5);
        sortList(head);
    }
}
